Path with maximum minimum value [Binary Search + DFS, Dijkstra’s algorithm]¶
Time: O((MxN)xLog(MxN)); Space: O(MxN); medium
Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].
The score of a path is the minimum value in that path. For example, the value of the path 8 -> 4 -> 5 -> 9 is 4.
A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).
Example 1:
Input: A = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation:
The path with the maximum score is highlighted in yellow.
Example 2:
Input: A = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2
Example 3:
Input: A = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3
Notes:
1 <= R, C <= 100
0 <= A[i][j] <= 10^9
Hints:
From A[0][0], put element with index into maxHeap, sorted by element. Mark it as visited.
When polling out the currrent, check its surroundings. If not visited before, put it into maxHeap.
Until we hit the A[m-1][n-1].
[1]:
class Solution1(object):
"""
Binary search + DFS
Time: O(m * n * log(M*N)), m = len(A), n = len(A[0])
Space: O(m * n)
maxHeap add and poll takes O(Log(M*N)).
"""
def maximumMinimumPath(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def check(A, val, r, c, lookup):
if r == len(A)-1 and c == len(A[0])-1:
return True
lookup.add((r, c))
for d in directions:
nr, nc = r + d[0], c + d[1]
if 0 <= nr < len(A) and \
0 <= nc < len(A[0]) and \
(nr, nc) not in lookup and \
A[nr][nc] >= val and \
check(A, val, nr, nc, lookup):
return True
return False
vals, ceil = [], min(A[0][0], A[-1][-1])
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] <= ceil:
vals.append(A[i][j])
vals = list(set(vals))
vals.sort()
left, right = 0, len(vals)-1
while left <= right:
mid = left + (right-left)//2
if not check(A, vals[mid], 0, 0, set()):
right = mid-1
else:
left = mid+1
return vals[right]
[2]:
s = Solution1()
A = [
[5,4,5],
[1,2,6],
[7,4,6]
]
assert s.maximumMinimumPath(A) == 4
A = [
[2,2,1,2,2,2],
[1,2,2,2,1,2]
]
assert s.maximumMinimumPath(A) == 2
A = [
[3,4,6,3,4],
[0,2,1,1,7],
[8,8,3,2,7],
[3,2,4,9,8],
[4,1,2,0,0],
[4,6,5,4,3]
]
assert s.maximumMinimumPath(A) == 3
[3]:
import heapq
class Solution2(object):
"""
Dijkstra algorithm
Time: O(m * n * log(m * n))
Space: O(m * n)
"""
def maximumMinimumPath(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
max_heap = [(-A[0][0], 0, 0)]
lookup = set([(0, 0)])
while max_heap:
i, r, c = heapq.heappop(max_heap)
if r == len(A)-1 and c == len(A[0])-1:
return -i
for d in directions:
nr, nc = r + d[0], c + d[1]
if 0 <= nr < len(A) and \
0 <= nc < len(A[0]) and \
(nr, nc) not in lookup:
heapq.heappush(max_heap, (-min(-i, A[nr][nc]), nr, nc))
lookup.add((nr, nc))
return -1
[4]:
s = Solution2()
A = [
[5,4,5],
[1,2,6],
[7,4,6]
]
assert s.maximumMinimumPath(A) == 4
A = [
[2,2,1,2,2,2],
[1,2,2,2,1,2]
]
assert s.maximumMinimumPath(A) == 2
A = [
[3,4,6,3,4],
[0,2,1,1,7],
[8,8,3,2,7],
[3,2,4,9,8],
[4,1,2,0,0],
[4,6,5,4,3]
]
assert s.maximumMinimumPath(A) == 3